Suppose we modify binary_search so that instead of using the floor operation to find the middle element of the array, we use the ceiling operation (recall that the ceiling of a real number \(x\) is the smallest integer that is \(\geq x\)). The full code is shown below for convenience:

import math

def new_binary_search(arr, start, stop, target):
    if stop <= start:
        return None

    middle = math.ceil((start + stop) / 2)

    if arr[middle] == target:
        return middle
    elif arr[middle] < target:
        return new_binary_search(arr, middle + 1, stop, target)
    else:
        return new_binary_search(arr, start, middle, target)

Which of the following statements about the correctness of new_binary_search is true? You may assume that arr will be a list containing at least one number, and that the initial call to new_binary_search will be with start = 0 and stop = len(arr) - 1.

Consider the code below which claims to compute the maximum of the input array. Adopt the convention that the maximum of an empty array is \(-\infty\).

import math
def maximum(arr, start=0, stop=None):
    """Find the maximum of arr[start:stop]."""
    if stop is None:
        stop = len(arr)
    if stop - start == 0:
        return -float('inf')

    middle = math.floor((start + stop) / 2)
    left = maximum(arr, start, middle)
    right = maximum(arr, middle, stop)
    if left > right:
        return left
    else:
        return right

Will this code always return the correct answer (the maximum)? If yes, simply say so. If no, describe what might happen (recurse infinitely, return the wrong answer, raise an index error, etc.).

Consider the code below which claims to compute the most common element in the array, returning a pair: the element along with the number of times it appears.

import math

def most_common(arr, start, stop):
    """Attempts to compute the most common element in arr[start:stop]."""
    if stop - start == 1:
        return (arr[start], 1)

    middle = math.floor((start + stop) / 2)

    left_value, left_count = most_common(arr, start, middle)
    right_value, right_count = most_common(arr, middle, stop)

    if left_count > right_count:
        return (left_value, left_count)
    else:
        return (right_value, right_count)

You may assume that the function is always called on a non-empty array, and with start = 0 and stop = len(arr). Will this code always return the correct answer (the most common element)?

Suppose we modify binary_search so that instead of using the floor operation to find the middle element of the array, we use the ceiling operation (recall that the ceiling of a real number \(x\) is the smallest integer that is \(\geq x\)). The full code is shown below for convenience:

import math

def new_binary_search(arr, start, stop, target):
    if stop <= start:
        return None

    middle = math.ceil((start + stop) / 2)

    if arr[middle] == target:
        return middle
    elif arr[middle] < target:
        return new_binary_search(arr, middle + 1, stop, target)
    else:
        return new_binary_search(arr, start, middle, target)

You may assume that arr will be a sorted list containing at least one number, and that the initial call to new_binary_search will be with start = 0 and stop = len(arr).